#include <iostream>
#include <string.h>
#include <vector>
#include <math.h>
using namespace std;


struct item{
	int w,v;
};



int main(){
	int t,m;
	cin>>t>>m;
	vector<item> a[m];
	int dp[m+1][t+1];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<m;i++){
		int c;
		item l;
		cin>>l.w>>l.v>>c;
		c--;
//		l.v=b;
//		l.w=a;
		a[c].push_back(l);
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=t;j++){
			dp[i][j] = dp[i-1][j];
			for(int k=0;k<a[i-1].size();k++){
//				cout<<"i)"<<i<<" j)"<<j<<" k)"<<k<<endl;
				dp[i][j] = max(dp[i][j],j-a[i-1][k].w>=0?dp[i-1][j-a[i-1][k].w]+a[i-1][k].v:0);
			}
		}
	}
//	for(int i=0;i<=m;i++){
//		for(int j=0;j<=t;j++){
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	cout<<dp[m][t];
	return 0;
}
